package offer;

/**
 * @Author Elephas
 * @Date 2022/1/14
 **/
@FunctionalInterface
public interface Search {
    /**
     * 在一个给定数组递增数组 nums 中寻找指定数 target，如果存在，返回其出现次数
     * @param nums
     * @param target
     * @return
     */
    int search(int[] nums,int target);
}

class SearchImpl1 implements Search{
    static final int[] TEST_01 = new int[]{5,7,7,8,8,10};
    public static void main(String[] args) {
        int res = new SearchImpl1().search(TEST_01,8);
        System.out.println(res);
    }

    @Override
    /**
     *  实现思路，两次二分查找，一次寻找最左侧位置，另一次寻找最右侧位置。
     */
    public int search(int[] nums, int target) {
        int lowBoundary = binarySearchBoundary(nums,target,true);
        if(lowBoundary == -1){
            return 0;
        }else{
            int highBoundary = binarySearchBoundary(nums,target,false);
            return highBoundary - lowBoundary + 1;
        }
    }
    private int binarySearchBoundary(int[] nums,int target,boolean isLowBoundary){
        int low = 0,high = nums.length - 1, mid = 0;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else{
                // 寻找下界
                if(isLowBoundary){
                    if(mid == 0){
                        break;
                    }else if(nums[mid] == nums[mid - 1]){
                        high = mid - 1;
                    }else{
                        break;
                    }
                }else{
                    //寻找上界
                    if(mid == nums.length -1){
                        break;
                    }else if(nums[mid] == nums[mid + 1]){
                        low = mid + 1;
                    }else{
                        break;
                    }
                }
            }
        }
        if(low <= high){
            return mid;
        }else{
            return -1;
        }
    }
}
